import java.util.Scanner;


//十六进制转八进制
public class zhuan8 {
    public static void main(String[] args) {
        Scanner in =new Scanner(System.in);
        int e=in.nextInt();
        String[] a=new String[100000];
        for (int t = 0; t <e ; t++) {
           a[t] = in.next();
        }
        for (int t = 0; t <e ; t++) {
            StringBuffer aa = new StringBuffer();
            char[] b = a[t].toCharArray();
            for (int i = 0; i < b.length; i++) {
                if (b[i] == 'F') aa.append("1111");
                if (b[i] == 'E') aa.append("1110");
                if (b[i] == 'D') aa.append("1101");
                if (b[i] == 'C') aa.append("1100");
                if (b[i] == 'B') aa.append("1011");
                if (b[i] == 'A') aa.append("1010");
                if (b[i] == '9') aa.append("1001");
                if (b[i] == '8') aa.append("1000");
                if (b[i] == '7') aa.append("0111");
                if (b[i] == '6') aa.append("0110");
                if (b[i] == '5') aa.append("0101");
                if (b[i] == '4') aa.append("0100");
                if (b[i] == '3') aa.append("0011");
                if (b[i] == '2') aa.append("0010");
                if (b[i] == '1') aa.append("0001");
                if (b[i] == '0') aa.append("0000");
            }
            String w = aa.toString();
            char[] c = w.toCharArray();
            long n = 0;
            long j = 1;
            for (int y = c.length - 1; y >= 0; y--) {
                if (c[y] == '1') {
                    n = n + j;
                }
                j = j * 2;
            }
            long d;
            String str = "";
            if (n == 0) System.out.print("0");
            while (n > 0) {
                d = n % 8;
                str = d + str;
                n = n / 8;
            }
            System.out.println(str);
        }
    }
}
